Chủ đề này có 101 trả lời

[gadget]

http://reflections.a...2006_2_zach.pdf
Đây là một bài viết khá hay về phương pháp hàm sinh

[gadget]

thầy có thể nói rõ hơn về ứng dụng của công thức nghịch đảo mobius không

[MrMATH]

Theo Erdos thì Chúa có 1 cuốn sách ghi toàn những lời giải như vậy

Các anh em ở gần Viện Toán Học có thể tìm đọc cuốn Proff from the book để hiểu rõ hơn về câu nói này

Hôm nay dắt chuột đi du lịch, gặp bài viết của clmt nên quote ra đây, có gì hứng thú các anh em cứ ... tự nhiên

Thêm 1 thông tin nữa là về tổ hợp thì trên viện cũng còn 1 cuốn khác, sơ cấp và chứa đầy các kết quả xem mà lác hết cả mắt trái lẫn mắt phải. Tên sách là Extrenal Combinatorics (and application in computer science). Tác giả thì ko nhớ rõ lắm, anh em nào có thời gian thì vào trích dẫn như clmt cho ... vui vẻ cả nhà nhỉ

[Mr.hoang]

chả lẽ kết thúc box ở đây à!
anh Dũng đã tổng hợp xong chua!

[dam_me2005]

Ai đó viết qua về pp đếm sử dụng công thức nghịch đảo Mobius và lý thuyết Polya đi .

Bạn có thể tìm đọc ở cuốn Lý Thuyết Tổ Hợp Và Đồ Thị của thầy Ngô Đắc Tân ở viện toán, mình thấy cuốn này viết rất hay. Bạn thử tìm đọc xem

[Gia Cát Lượng]

Có ai có thể cho mình lời giải cụ thể về bài tổ hợp trong VMO bảng B năm nay được không?

[hophu]

Ai chỉ giùm em cách giải bài toán về số Câtlan(bài toán các cung tròn)với.cảm ơn!

[tmbtw]

Từ đây toppic này đi rồi
Không còn ai muốn thảo luận nữa sao ?

[namdung]

Ai chỉ giùm em cách giải bài toán về số Câtlan(bài toán các cung tròn)với.cảm ơn!

Bài này phát biểu như sau: Có 2n điểm nằm trên đường tròn. Có bao nhiêu cách nối các điểm này bằng n cung sao cho không có 2 cung nào cắt nhau.

Giải: Gọi c_n là số cách nối như vậy. Quy ước c_0 = 1. Ta đánh số các điểm là 1, 2, 3, ..., 2n. Xét điểm 1. Rõ ràng 1 chỉ có thể được nối với các điểm chẵn: 2, 4, ..., 2n. Nếu 1 nối với 2k thì cung này chia 2n-2 điểm còn lại thành 2 phần, 1 phần có 2k-2 điểm và 1 phần có 2n-2k điểm. Từ đây ta suy ra công thức truy hồi

$c_n = c_0*c_{n-1} + c_1*c_{n-2} + ... + c_{n-1}*c_0 $

Để giải công thức truy hồi này, ta xét hàm sinh

$f(x) = c_0 + c_1*x + ...+ c_n*x^n + ...$

Xét f(x)*f(x). Sử dụng công thức nhân hai hàm sinh và công thức ta suy ra

$(f(x))^2 = 1 + c_2*x + c_3*x^2 + ... = (f(x) - 1)/x$

Từ đó suy ra

$ f(x) = \dfrac{1 - \sqrt{1-4x}}{2x}$

Từ đó, sử dụng công thức nhị thức Newton mở rộng

$ (1+x)^a = 1 + ax + a(a-1)x^2/2 + ... $

ta suy ra công thức Catalan nổi tiếng

$ c_n = \dfrac{1}{n+1}C^n_{2n}$

Bài viết đã được chỉnh sửa nội dung bởi inhtoan: 11-06-2009 - 10:19

[namdung]

Từ đây toppic này đi rồi
Không còn ai muốn thảo luận nữa sao ?

Xin lỗi các bạn vì người tạo ra chủ đề đã không hoàn thành nhiệm vụ dẫn dắt chủ đề. Tôi sẽ cố gắng để tiếp tục các định hướng đã đặt ra: viết các bài viết tổng hợp về các phương pháo. Tuy nhiên, tôi vẫn đang rất cần những cộng tác viên, vì khối lượng công việc là rất lớn. Trước mắt, tôi sẽ viết 1 bài về phương pháp hàm sinh. Ai sẽ nhận trách nhiệm viết bài về các phương pháp khác đây?

[Lumpy]

Thưa thầy,em có đọc được một phươgn pháp Division Rule từ tài liệu nước ngoài,nôm na là như sao:Nếu B là một tập hữu hạn phần tử f:A->B sao cho với mọi b thuộc B ta đều có $ |f^{-1}(b)|=k $thì |A|=k|B|.Thành thử nếu xét k bằng 1 thì f là song ánh nên |A|=|B| đó có phải là mở rộng của phương pháp song ánh phải không thầy?

Bài viết đã được chỉnh sửa nội dung bởi inhtoan: 11-06-2009 - 10:20

[namdung]

Chắc là thế rồi.

Ví dụ bài vô địch Mỹ 96: Gọi a_n là số các xâu nhị phân độ dài n không chứa xâu con 010 và b_n là số các xâu nhị phân độ dài n không chứa các xâu con 0011 hoặc 1100. Chứng minh rằng b_{n+1} = 2a_n.

[kyoshiro_hp]

thưa thầy, em hơi có 1 chút thắc mắc. Em thấy anh Trường có nói ở trên là PP hàm
sinh ko hề sơ cấp, vậy ko biết nó có phù hợp với phổ thông, cụ thể là có được dùng khi thi HSG ko ạ?

[Mr.hoang]

uh! nó ko sơ cấp!l lên đại học bạn sẽ tha hồ nghiên cứu!
có lẽ bây giờ nên biết ; ý bạn nói là thi quốc gia phai ko?
đề của VN tôi thấy ngay cả hệ cơ số cũng ko ra ; thì mấy cái lung tung này sẽ chẳng ra đâu!
ta ra đề rất giở đặc biệt là sh; ví dụ là mấy năm liền gần đây số học ra toàn là giải PPNN chả hay ho gì!

[Mr.hoang]

uh! nó ko sơ cấp!l lên đại học bạn sẽ tha hồ nghiên cứu!
có lẽ bây giờ nên biết ; ý bạn nói là thi quốc gia phai ko?
đề của VN tôi thấy ngay cả hệ cơ số cũng ko ra ; thì mấy cái lung tung này sẽ chẳng ra đâu!
ta ra đề rất giở đặc biệt là sh; ví dụ là mấy năm liền gần đây số học ra toàn là giải PPNN chả hay ho gì!

[namdung]

Đúng là phương pháp hàm sinh sẽ không ra đâu. Nhưng những bài áp dụng tư tưởng của PP hàm sinh thì có thể chứ.

Còn đề của mình chưa hay là đúng rồi. Vì muốn có 1 đề hay, tốn nhiều công sức lắm, mà có ai ai cũng sẵn sàng bỏ công sức ra để làm việc đó đâu.

[namdung]

Dear các bạn,

Tôi gửi đính kèm bài viết của tôi đã được bổ sung thêm đôi chút.

Bài này tôi đã trình bày tại trường ĐHKHTN hồi tháng 8 vừa qua.

Tôi gửi luôn file word để mọi người tiện sử dụng.

File gửi kèm

•  Coungting_Namdung.doc   171.5K   383 Số lần tải

[CTptnk]

Dear các bạn,

Tôi gửi đính kèm bài viết của tôi đã được bổ sung thêm đôi chút.

Bài này tôi đã trình bày tại trường ĐHKHTN hồi tháng 8 vừa qua.

Tôi gửi luôn file word để mọi người tiện sử dụng.

Topic này off lâu quá rồi nhỉ?
Làm sao em có thể đọc mấy file word của thầy Namdung bây giờ?
Em mở ra và chọn tất cả các font chữ đều thấy một mớ kí hiệu lộn xộn!
Các anh em giúp với!

[kyoshiro_hp]

Bạn mở ra rồi click vào biểu tượng W ở góc trên cùng bên phải ( chắc là vậy). Topic này off lâu vậy có lẽ vì bây giờ ai cũng bận cả, ko biết thảo luận tiếp cái gì.

Bài viết đã được chỉnh sửa nội dung bởi kyoshiro_hp: 13-09-2006 - 09:30

[lyxuansang91]

Thực ra thì tôi cũng chỉ muốn đưa ra những vấn đề để chúng ta cùng xây dựng, chứ không có tham vọng viết được cái gì công phu. Tư tưởng của phương pháp song ánh rất đơn giản: nếu tồn tại song ánh f từ A vào B thì |A| = |B|. Ngoài ra, nếu s = |A|, t = |A| thì s = t. Nó cũng đơn giản như nguyên lý Dirichlet vậy đó. Quan trọng là biết cách áp dụng vào các bài toán.

Phương pháp quỹ đạo, cái này tôi gọi theo lịch sử, thầy Đỗ Đức Thái ngày xưa gọi như vậy, là phương pháp quy các bài toán đếm về các bài toán đếm số đường đi trên lưới nguyên. Trong phương pháp này, có một nguyên lý rất hay gọi là nguyên lý đối xứng gương (ví dụ VNTST 2003, bài 1). Định lý cơ bản của phương pháp này là số đường đi ngắn nhất trên lưới nguyên từ (0, 0) đến (m, n) bằng C(m, m+n).

Phương pháp thêm bớt là Principle of exclusion and inclusion là phép đếm sử dụng công thức mở rộng của công thức |A hợp B| = |A | + |B| - |A     B| và thể hiện thường thấy nhất là trong lý thuyết đa thức xe (trong giáo trình Toán rời rạc nâng cao hoặc trong cuốn Tìm tòi để học toán của Lê Quang Nẫm có trình này).

Tất cả những điều này không có gì mới. Mục đích của tôi là cùng chia sẻ và trao đổi với các bạn về những phương pháp này.

em thấy cái này thầy có thể viết rõ hơn được không???Chứ em thấy khó hiểu quá (mới học sinh lớp 10 mà)